class Solution(object):
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        length = len(s)
        DP = [[True for _ in range(length)] for _ in range(length)]
        for k in range(1, 2 * (length - 1)):
            upper = k // 2
            for i in range(upper, max(-1, k - length), -1):
                if i + 1 == k - i:
                    DP[i][k - i] = (s[i] == s[k - i])
                else:
                    if i + 1 < k - i:
                        DP[i][k - i] = (DP[i + 1][k - i - 1] and s[i] == s[k - i])

        M = [1 for _ in range(length)]
        for i in range(1, length):
            if DP[0][i]:
                M[i] = 1
            else:
                min_val = i + 1
                for j in range(0, i):
                    if DP[j + 1][i]:
                        min_val = min(min_val, 1 + M[j])
                M[i] = min_val
        return M[-1] - 1


data = Solution()
s = "ab"
print(data.minCut(s))
